In modern computer systems, many users often share a common block (i.e., section) of memory so that a highly efficient use of the memory is achieved. That is, oftentimes, users only need access to the memory for a short period of time, so it would be highly inefficient to totally dedicate portions of the memory block to particular users even during times when such users are not requesting access to the memory. Instead, when a user wishes to use a part of the memory block, the user makes a request to a storage manager which temporarily allocates a portion of the memory block to the requesting user. When the requesting user is finished with the allocated portion, the storage manager releases the allocated portion so that a future request (possibly from a different user) can now use this portion of the memory block.
An example of a conventional system will now be described with reference to FIGS. 1, 2 and 3. In FIG. 1, a plurality of requesting applications (11a, 11b, 11c), are simultaneously requesting access to a block of memory within memory 13, which could be semiconductor memory, a hard disk, or any other type of memory. The requesting applications must first contact a storage manager 12 which performs the function of temporarily allocating portions of the memory block to each requesting application. For example, as shown in FIG. 2, the storage manager temporarily assigns area 21 of memory block 131 to requesting application 11a, area 22 to application 11b and area 23 to application 11c. If application 11a uses up its allocated area 21 and needs more space, the storage manager assigns a new area 31 (see FIG. 3) to application 11a. Similarly, if applications 11b and 11c request more space, areas 32 and 33, respectively, are assigned thereto by the storage manager 12.
As can be seen in FIG. 3, the memory block 131 soon becomes cluttered with assigned areas. As more and more areas become assigned to requesting applications, the memory is said to become "fragmented" since the available space has been split up so many times between the same few applications. A major problem with this system is that a new requesting application may not be able to have space allocated to it, since the previous applications have been allocated space that extends throughout the block 131. Although there is space in between the allocated areas (e.g., between areas 31 and 32) this space soon closes in as more areas are allocated and soon such spaces become very small. This inefficiency is known as external fragmentation.
One solution to this fragmentation problem is to provide an initial free area (41, 42, 43 in FIG. 4) to each requesting application (11a, 11b, 11c, respectively). When a requesting application makes a first request to the storage manager 12 for a memory area, the requesting application informs the storage manager of the amount of memory that it will require for the lifetime of the particular session in which the application needs the use of the memory. The storage manager then allocates an area of this size to the application. As the application makes requests for storage, all of the requests are satisfied from the initial free area assigned to that requesting application. This greatly reduces the fragmentation problem since all of an application's assigned memory areas are confined to the initial free area, thus preventing the storage manager from assigning a particular application memory areas interspersed throughout the block.
However, this technique is disadvantageous in that the requesting application must provide the storage manager with the amount of memory space that will be needed by that application, thus imposing a burden on the requesting application. For example, this may entail the requesting application keeping statistics from previous runs. This presents a drain on the requesting application's processing power, and the application is thus diverted from focusing on its core functions.
Further, if the requesting application requests too much space, then an inefficiency known as internal fragmentation results wherein allocated space in the initial free area goes unused by the requesting application and is thus also unusable by other applications. If the requesting application requests not enough space, the storage manager will begin to assign areas outside of the initial free area to the application, resulting in the external fragmentation described above.